package chapter2;

import util.PrintUtils;

/**
 * merge sort 归并排序
 */
public class mergeSort {

    public void sort(int[] arr, int p, int q, int[] tmp) {
        if (p < q) {
            int m = (p+q+1)/2;
            sort(arr, p, m - 1, tmp);
            sort(arr, m, q, tmp);
            merge(arr, p, m, q, tmp);
        }
    }

    public void merge(int[] arr, int p, int m, int q, int[] tmp) {
        int p1 = p, m1 = m;

        int t = 0;
        while (p1 < m && m1 <= q) {
            if (arr[p1] < arr[m1]) {
                tmp[t++] = arr[p1++];
            } else {
                tmp[t++] = arr[m1++];
            }
        }

        while (p1 < m) {
            tmp[t++] = arr[p1++];
        }

        while (m1 <= q) {
            tmp[t++] = arr[m1++];
        }

        for (int i = q; i >= p; i--) {
            arr[i] = tmp[--t];
        }
    }


    public static void main(String[] args) {
        int[] arr = {31, 41, 59, 26, 41, 58,1};
        new mergeSort().sort(arr, 0, arr.length-1, new int[arr.length]);
        PrintUtils.PrintArray(arr);
    }
}
